package uu.game.util;

import java.lang.reflect.Array;

/**
 * 主要是关于数组的一些辅助方法<br/>
 * 大部分需要二次扫描，第一次确定需要构造的新数组的长度，第二次填充数据
 * 
 * @author uu
 * @version 2010-4-27 下午12:24:55
 */
public class ArrayUtils {

    /**
     * 使用int数组中的非0元素构造一个新数组<br/>
     * <br/>
     * 如果没有非0元素，返回int[0]
     * 
     * @param source
     *            要提取元素的数组
     * @return 新数组。如果传入的数组没有非0元素，返回int[0]
     */
    public static int[] copyArrayNot0(int[] source) {
        int sl = source.length;
        int length = 0;
        for (int i = 0; i < sl; i++)
            if (source[i] != 0)
                length++;
        int[] a = new int[length];
        for (int i = 0, j = 0; i < sl; i++) {
            int e = source[i];
            if (e != 0)
                a[j++] = e;
        }
        return a;
    }

    /**
     * 使用T数组中的非null元素构造一个新数组<br/>
     * <br/>
     * 如果没有非null元素，返回T[0]
     * 
     * @param source
     *            要提取元素的数组
     * @return 新数组。如果传入的数组没有非null元素，返回T[0]
     */
    @SuppressWarnings("unchecked")
    public static <T> T[] copyArrayNotNull(T[] source) {
        int sl = source.length;
        int length = 0;
        for (int i = 0; i < sl; i++)
            if (source[i] != null)
                length++;
        Class<T> componentType = (Class<T>)source.getClass().getComponentType();
        T[] a = newArray(componentType, length);
        for (int i = 0, j = 0; i < sl; i++) {
            T e = source[i];
            if (e != null)
                a[j++] = e;
        }
        return a;
    }

    /**
     * 得到两个数组从某位置开始的交集，存放于一个新数组<br/>
     * 如果没有交集，返回int[0]<br/>
     * 需要保证两个数组需要求交集的部分已排序，如果未排序，会得到不可预期的结果
     * 
     * @param a1
     *            第一个数组
     * @param from1
     *            第一个数组的开始位置
     * @param a2
     *            第二个数组
     * @param from2
     *            第二个数组的开始位置
     * @return 两个数组的交集。如果没有交集，返回int[0]
     */
    public static int[] interception(int[] a1, int from1, int[] a2, int from2) {
        int l1 = a1.length;
        int l2 = a2.length;
        if (l1 - from1 <= 0 || l2 - from2 <= 0
         || a1[l1 - 1] < a2[from2] || a1[from1] > a2[l2 - 1])
            return new int[0];
        int i1 = from1;
        int i2 = from2;
        int e1;
        int e2;
        int l = 0;
        while (i1 < l1 && i2 < l2) {
            e1 = a1[i1];
            e2 = a2[i2];
            if (e1 < e2)
                i1++;
            else if (e1 > e2)
                i2++;
            else {
                l++;
                i1++;
                i2++;
            }
        }
        int[] a = new int[l];
        int i = 0;
        i1 = from1;
        i2 = from2;
        while (i < l) {
            e1 = a1[i1];
            e2 = a2[i2];
            if (e1 < e2)
                i1++;
            else if (e1 > e2)
                i2++;
            else {
                a[i++] = e1;
                i1++;
                i2++;
            }
        }
        return a;
    }

    /**
     * 得到两个数组从某位置开始的交集，存放于一个新数组<br/>
     * 如果没有交集，返回T[0]<br/>
     * 需要保证两个数组需要求交集的部分已排序，如果未排序，会得到不可预期的结果
     * 
     * @param a1
     *            第一个数组
     * @param from1
     *            第一个数组的开始位置
     * @param a2
     *            第二个数组
     * @param from2
     *            第二个数组的开始位置
     * @return 两个数组的交集。如果没有交集，返回T[0]
     * @see Comparable
     */
    @SuppressWarnings("unchecked")
    public static <T extends Comparable<? super T>> T[] interception(T[] a1, int from1,
            T[] a2, int from2) {
        Class<T> componentType = (Class<T>)a1.getClass().getComponentType();
        int l1 = a1.length;
        int l2 = a2.length;
        if (l1 - from1 <= 0 || l2 - from2 <= 0
         || a1[l1 - 1].compareTo(a2[from2]) < 0 || a1[from1].compareTo(a2[l2 - 1]) > 0)
            return newArray(componentType, 0);
        int i1 = from1;
        int i2 = from2;
        T e1;
        T e2;
        int l = 0;
        while (i1 < l1 && i2 < l2) {
            e1 = a1[i1];
            e2 = a2[i2];
            if (e1.compareTo(e2) < 0)
                i1++;
            else if (e1.compareTo(e2) > 0)
                i2++;
            else {
                l++;
                i1++;
                i2++;
            }
        }
        T[] a = newArray(componentType, l);
        int i = 0;
        i1 = from1;
        i2 = from2;
        while (i < l) {
            e1 = a1[i1];
            e2 = a2[i2];
            if (e1.compareTo(e2) < 0)
                i1++;
            else if (e1.compareTo(e2) > 0)
                i2++;
            else {
                a[i++] = e1;
                i1++;
                i2++;
            }
        }
        return a;
    }

    @SuppressWarnings("unchecked")
    private static <T> T[] newArray(Class<T> componentType, int length) {
        return (T[])Array.newInstance(componentType, length);
    }

}
